Multi-core computation of transfer matrices for strip lattices in the Potts model

摘要

The transfer-matrix technique is a convenient way for studying strip latticesin the Potts model since the compu- tational costs depend just on the periodicpart of the lattice and not on the whole. However, even when the cost isreduced, the transfer-matrix technique is still an NP-hard problem since thetime T(|V|, |E|) needed to compute the matrix grows ex- ponentially as afunction of the graph width. In this work, we present a paralleltransfer-matrix implementation that scales performance under multi-corearchitectures. The construction of the matrix is based on several repetitionsof the deletion- contraction technique, allowing parallelism suitable tomulti-core machines. Our experimental results show that the multi-coreimplementation achieves speedups of 3.7X with p = 4 processors and 5.7X with p= 8. The efficiency of the implementation lies between 60% and 95%, achievingthe best balance of speedup and efficiency at p = 4 processors for actualmulti-core architectures. The algorithm also takes advantage of the latticesymmetry, making the transfer matrix computation to run up to 2X faster thanits non-symmetric counterpart and use up to a quarter of the original space.